import sys

head, n = map(int, input().split())
mem = dict()
for i in range(n):
    addr, va, naddr = map(int, sys.stdin.readline().strip('\n').split())
    mem[addr] = (addr, va, naddr)
good_value = set()

good = []
bad = []
node = mem[head]
for i in range(n):
    if abs(node[1]) not in good_value:
        good.append(node)
        good_value.add(abs(node[1]))
    else:
        bad.append(node)

    if node[2] != -1:
        node = mem[node[2]]
    else:
        break
for i in range(len(good) - 1):
    print("%05d %d %05d" % (good[i][0], good[i][1], good[i + 1][0]))
print("%05d %d %d" % (good[-1][0], good[-1][1], -1))
if len(bad) != 0:
    for i in range(len(bad) - 1):
        print("%05d %d %05d" % (bad[i][0], bad[i][1], bad[i + 1][0]))
    print("%05d %d %d" % (bad[-1][0], bad[-1][1], -1))
